﻿/*
G 社交网络
分数 50
作者 朱允刚
单位 吉林大学
可以将n个QQ用户间的好友关系建模为一个包含n个顶点的无向图，顶点编号为1至n，每个顶点对应一个用户，若2个用户i和j是QQ好友，则在顶点i和j之间连接一条边，并根据用户间的亲密度对该边附以一个权值c
ij
​
 。在该图中，可以利用两个顶点间的最短路径长度衡量两个用户的关系密切程度，也可以利用经过一个顶点的最短路径数目来衡量一个用户在关系网络中的影响力，具体地，我们定义用户k在QQ关系网络中的“影响力”为：

333.png

其中N
ij
​
 为顶点i到j的最短路径数目，N
ijk
​
 为顶点i到j的所有最短路径中经过顶点k的最短路径数目（上述二值可能超出int型范围，请使用long long类型）。D
ij
​
 表示i到j的最短路径长度。

现给定一个如上描述的无向图，请编写程序，计算每个顶点的“影响力”，假定给定的图是连通的。

输入格式:
输入第一行为两个正整数n和e，分别表示图的顶点数和边数，接下来e行表示每条边的信息，每行为3个正整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。

n≤100，e≤5000，c≤1000，任意两点间的最短路径数目≤10
10


输出格式:
输出为n行，每行一个实数，精确到小数点后3位，第i行为顶点i的影响力。

输入样例:
4 4
3 2 6
4 3 1
1 3 9
4 1 1

输出样例:
0.000
0.000
30.000
20.000

解释:
对于顶点1：边2-3、3-4、2-4的最短路径均不经过顶点1，故顶点1的影响力为0.

对于顶点3：
顶点1到2的最短路径共1条，长度为8，经过点3，顶点2到4的最短路径共1条，长度为7，经过点3，顶点1到4的最短路径共1条，但不经过点3。
故f(3)=D
12
​
 ∗1+D
24
​
 ∗1+D
14
​
 ∗0+D
21
​
 ∗1+D
42
​
 ∗1+D
41
​
 ∗0=8+7+0+8+7+0=30.000

提示:
若顶点a到顶点b有x条路径，点b到点c有y条路径，则a经过b到达c的路径有x*y条。

代码长度限制
16 KB
时间限制
50 ms
内存限制
64 MB
*/

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <iomanip>

using namespace std;

const long long INF = numeric_limits<long long>::max();

struct Edge {
    int to;
    long long weight;
};

void dijkstra(int start, const vector<vector<Edge>>& graph, vector<long long>& distance, vector<long long>& shortestPaths) {
    int n = graph.size();
    distance.assign(n, INF);
    shortestPaths.assign(n, 0);

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({ 0, start });
    distance[start] = 0;
    shortestPaths[start] = 1;

    while (!pq.empty()) {
        int u = pq.top().second;
        long long dist_u = pq.top().first;
        pq.pop();

        if (dist_u > distance[u]) {
            continue;
        }

        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            long long weight = edge.weight;

            if (distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
                shortestPaths[v] = shortestPaths[u];
                pq.push({ distance[v], v });
            }
            else if (distance[u] + weight == distance[v]) {
                shortestPaths[v] += shortestPaths[u];
            }
        }
    }
}

int main() {
    int n, e;
    cin >> n >> e;

    vector<vector<Edge>> graph(n);
    vector<long long> distance, shortestPaths;

    for (int i = 0; i < e; ++i) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        graph[a - 1].push_back({ b - 1, c });
        graph[b - 1].push_back({ a - 1, c });
    }

    for (int i = 0; i < n; ++i) {
        dijkstra(i, graph, distance, shortestPaths);
        double influence = 0.0;

        for (int j = 0; j < n; ++j) {
            if (i != j) {
                influence += (double)(shortestPaths[j] * distance[j]) / (double)distance[i];
            }
        }

        cout << fixed << setprecision(3) << influence << endl;
        /*
        setprecision 是 <iomanip> 头文件中的一个函数，用于设置输出流的精度，控制输出浮点数的小数点后的位数。在这个程序中，cout << fixed << setprecision(3) << influence << endl; 表示输出 influence 变量，并设置其小数点后的位数为 3。这样可以保证输出的浮点数精确到小数点后三位。
        */
    }

    return 0;
}
/*
这个程序使用 Dijkstra 算法计算最短路径和最短路径数目。遍历每个顶点，分别计算其影响力。
*/